package main

/*
	给定一个由0和1组成的矩阵mat，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离
	两个相邻元素间的距离为1
*/
var(
	dddx = [4]int{0,0,-1,1}
	dddy = [4]int{-1,1,0,0}
)
//广度优先搜索
//func updateMatrix(mat [][]int) [][]int{
//	m := len(mat)
//	n := len(mat[0])
//	queue := [][]int{}
//	for i:=0;i<m;i++{
//		for j:=0;j<n;j++{
//			if mat[i][j]==0{
//				//将所有的0进入队列
//				queue = append(queue, []int{i,j})
//			}else{
//				// -1代表该块未被遍历过
//				mat[i][j]=-1
//			}
//		}
//	}
//	for len(queue)>0{
//		//取出0
//		point := queue[0]
//		queue = queue[1:]
//		newx,newy := 0,0
//		for i:=0;i<4;i++{
//			newx = point[0]+dddx[i]
//			newy = point[1]+dddy[i]
//			if newx>=0&&newx<m&&newy>=0&&newy<n&&mat[newx][newy]==-1{
//				mat[newx][newy] = mat[point[0]][point[1]]+1
//				queue = append(queue,[]int{newx,newy})
//			}
//		}
//	}
//	return mat
//}

//动态规划
func updateMatrix(mat [][]int) [][]int{
	m := len(mat)
	n := len(mat[0])
	for i:=0;i<m;i++{
		for j:=0;j<n;j++{
			if mat[i][j]==0{
				mat[i][j]=0
			}else{
				//未遍历块
				mat[i][j]=10000
			}
		}
	}
	//向左向上
	for i:=0;i<m;i++ {
		for j := 0; j < n; j++ {
			if i>0{
				mat[i][j] = getmin(mat[i-1][j]+1,mat[i][j])
			}
			if j>0{
				mat[i][j] = getmin(mat[i][j-1]+1,mat[i][j])
			}
		}
	}
	//向右向下
	for i:=m-1;i>=0;i-- {
		for j := n-1; j >=0; j-- {
			if i<m-1{
				mat[i][j] = getmin(mat[i+1][j]+1,mat[i][j])
			}
			if j<n-1{
				mat[i][j] = getmin(mat[i][j+1]+1,mat[i][j])
			}
		}
	}
	return mat
}
func getmin(a,b int) int{
	if a>b{
		return b
	}else{
		return a
	}
}
func main(){
	mat := [][]int{
		{0,0,0},
		{0,1,0},
		{1,1,1},
	}
	print(updateMatrix(mat))
}